#include<iostream>
#include<cassert>
using namespace std;

template<class T>
struct AVLTreeNode
{
	AVLTreeNode(const T& k = T())
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_data(k)
		,_bf(0)
	{}
	AVLTreeNode<T>* _left;
	AVLTreeNode<T>* _right;
	AVLTreeNode<T>* _parent;
	T _data;
	int _bf;
};

template<class T>
class AVLTree
{
	typedef AVLTreeNode<T> Node;
public:
	AVLTree()
		:_root(nullptr)
	{}
	bool Insret(const T& k)
	{
		if (_root == nullptr)
		{
			_root = new Node(k);
			return true;
		}

		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (k < cur->_data)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (k == cur->_data)
			{
				parent = cur;
				return false;
			}
			else
			{
				parent = cur;
				cur = cur->_right;
			}
		}
		//找到位置，开始插入
		cur = new Node(k);
		if (k < parent->_data)////////
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		cur->_parent = parent;

		//控制平衡
		//1.更新平衡因子 --- 新增节点到根节点的祖先路径
		//2.出现异常平衡因子 --- 旋转平衡处理
		while (parent)
		{
			if (parent->_left == cur)
			{
				parent->_bf--;
			}
			else
			{
				parent->_bf++;
			}

			if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				//继续向上更新
				cur = parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				//进行旋转
				//右单旋
				if (parent->_bf == -2 && cur->_bf == -1)
				{
					RotateR(parent);
				}
				//左单旋
				else if (parent->_bf == 2 && cur->_bf == 1)
				{
					RotateL(parent);
				}
				//左右双旋
				else if (parent->_bf == -2 && cur->_bf == 1)
				{

				}
				//右左双旋
				else if (parent->_bf == 2 && cur->_bf == -1)
				{

				}
				else
				{
					assert(false);
				}
				break;
			}
			else
			{
				assert(false);
			}
		}
		return true;
	}
private:
	//左单旋
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		Node* PParent = parent->_parent;
		//subRL 和 parent
		parent->_right = subRL;
		if(subRL)
			subRL->_parent = parent;
		//parent 和 subR
		subR->_left = parent;
		parent->_parent = subR;
		if (_root == parent)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (PParent->_left == parent)
			{
				PParent->_left = subR;
			}
			else
			{
				PParent->_right = subR;
			}
		}
		subR->_bf = parent->_bf = 0;
	}
	//右单旋
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* PParent = parent->_parent;
		//subLR 和 parent
		parent->_left = subLR;
		if(subLR)
			subLR->_parent = parent;
		//parent 和 subL
		subL->_right = parent;
		parent->_parent = subL;
		if (_root == parent)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (PParent->_left == parent)
			{
				PParent->_left = subL;
			}
			else
			{
				PParent->_right = subL;
			}
		}
		subL->_bf = parent->_bf = 0;
	}
	//左右双旋
	void RotateLR(Node* parent)
	{
		RotateL(parent->_left);
		RotateR(parent);
	}
	//右左双旋
	void RotateRL(Node* parent)
	{
		RotateR(parent->_right);
		RotateL(parent);
	}
private:
	Node* _root;
};

int main()
{
	AVLTree<int> T;
	//T.Insret(60);
	//T.Insret(30);
	//T.Insret(90);
	//T.Insret(20);
	//T.Insret(40);
	//T.Insret(10);//右旋没问题
	//T.Insret(60);
	//T.Insret(30);
	//T.Insret(90);
	//T.Insret(70);
	//T.Insret(100);
	//T.Insret(110);//右旋没问题

	return 0;
}